package com.leetcode.algorithm.y22.m09.w1;

/**
 * 134. 加油站
 * 
 * https://leetcode.cn/problems/gas-station/
 * 
 * @author jie.deng
 *
 */
class Question0134Solution02 {

	public int canCompleteCircuit(int[] gas, int[] cost) {
		int len = gas.length;
		// 从第0个加油站出发
		int startIdx = 0;
		// 从起点出发，油箱最后剩余的油量
		int remainSum = 0;
		// 从起点出发，油箱里的油量最小值
		int minRemain = 0;
		for (int idx = 0; idx < len; idx++) {
			remainSum += (gas[idx] - cost[idx]);
			if (remainSum < minRemain) {
				minRemain = remainSum;
			}
		}
		if (minRemain == 0) {
			// 从第0个加油站出发累加没有出现负数
			return startIdx;
		}
		if (remainSum < 0) {
			// gas的总和小于cost总和，那么无论从哪里出发，一定是跑不了一圈的
			return -1;
		}
		// 从第i个加油站出发,走到第0个加油站，需要至少(-minRemain)，才能保证跑一圈
		int remain = 0;
		for (startIdx = len - 1; startIdx > 0; startIdx--) {
			remain += (gas[startIdx] - cost[startIdx]);
			if (remain + minRemain >= 0) {
				return startIdx;
			}
		}
		return -1;
	}

}